package work.lianbiao;

import work.ListNode;

public class Problem148 {

    //冒泡排序timeout
    public ListNode sortList1(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        Integer length = getLength(head);
        ListNode myNode = head;
        ListNode listNode = dummy;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length - i - 1; j++) {
                if (myNode.val > myNode.next.val) {
                    listNode.next = myNode.next;
                    myNode.next = myNode.next.next;
                    listNode.next.next = myNode;
                    listNode = listNode.next;
                } else {
                    listNode = listNode.next;
                    myNode = myNode.next;
                }
            }
            listNode = dummy;
            myNode = dummy.next;
        }
        return dummy.next;
    }


    public Integer getLength(ListNode head) {
        int sum = 0;
        while (head != null) {
            head = head.next;
            sum = sum + 1;
        }
        return sum;
    }

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode mid = middleNode(head);
        //这是左边排序好的东西
        ListNode right = sortList(head);
        //这是右边边排序好的东西
        ListNode left = sortList((mid));
//合并+排序
        ListNode ans = mergeTwoLists(left, right);
        return ans;

    }

    private ListNode middleNode(ListNode head) {
        //用于记录慢指针的前一个节点
        ListNode pre = head;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        return slow;
    }

    private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1 != null ? list1 : list2;
        return dummy.next;
    }

    public static void main(String[] args) {
        int[] a = {4, 1, 3, 2};
        ListNode listNode = ListNode.listNodeFromArray(a);
        Problem148 problem148 = new Problem148();
        ;
        ListNode.printList(problem148.sortList(listNode));

    }
}
